今天講二元樹的刪除，特別拉一篇出來講，是因為它滿複雜，要處理的case很多。

樹的刪除這邊會把它分成4個case

1. 左右的child都為空
   

刪45，45的左右child都為空，直接把30的右child改為空

2. 左邊的child有值，但右節點為空
   

刪14，14有左child但沒有右child，把1拉上去，30的左child接到1

3. 右邊child有值，但它底下沒有左child
   

刪45，45有右child 60，但60底下沒有左child，那就把60拉上去，60的左child接38，30的右child接60

4. 右邊child有值，底下有左child
   

這時候的情境比較複雜，我們需要找右邊child底下最小的值，往右邊child的左child做搜尋，找到最小的值。大家可以試試看如果用54或73做替換，再用樹搜尋一下51，你會發現二元樹的特性被破壞，導致有些值永遠找不到。

刪45，右child不為空，而且60擁有左child，往左child找最小值，找到51，把51拉上來，58的左child接到54，51的左child接38 右child接60，30的右child接51。

4個case都講完了，就可以轉化為程式
這邊會做leetcode的450題，leetcode有大量test case，如果都過了就證明沒問題～

Leetcode #450. Delete Node in a BST

程式

func deleteNode(root *TreeNode, key int) *TreeNode {
	var preNode *TreeNode
	currentNode := root

	// 先找到要刪的節點
	for {
		// 找不到
		if currentNode == nil {
			return root
		}
        
		if currentNode.Val == key {
			break
		}
        
		if key < currentNode.Val {
			// 往左找
			preNode = currentNode
			currentNode = currentNode.Left
		} else {
			// 往右找
			preNode = currentNode
			currentNode = currentNode.Right
		}
	}

	// case.1 左右chil為空
	if currentNode.Left == nil && currentNode.Right == nil {
		// 刪的是root節點
		if preNode == nil {
			root = nil
			return root
		}

		if currentNode.Val < preNode.Val {
			preNode.Left = nil
		} else {
			preNode.Right = nil
		}

		return root
	}

	// case.2 左child有東西 右child為空
	if currentNode.Left != nil && currentNode.Right == nil {
		// 刪的是root節點
		if preNode == nil {
			root = currentNode.Left
			return root
		}

		// 判斷要接到上一個節點的左邊還是加邊
		if currentNode.Val < preNode.Val {
			preNode.Left = currentNode.Left
		} else {
			preNode.Right = currentNode.Left
		}

		return root
	}

	// case.3 右child有東西 但它沒有左child
	if currentNode.Right != nil && currentNode.Right.Left == nil {
		// 把目前節點的左child 接到右child的左child
		currentNode.Right.Left = currentNode.Left

		// 刪的是root節點
		if preNode == nil {
			root = currentNode.Right
			return root
		}

		// 判斷要接到上一個節點的左邊還是加邊
		if currentNode.Val < preNode.Val {
			preNode.Left = currentNode.Right
		} else {
			preNode.Right = currentNode.Right
		}

		return root
	}

	// case.4 右child擁有左child
	// 從左child開始找 找到最小的值
	leftMostParent := currentNode.Right
	leftMost := currentNode.Right.Left
	for leftMost.Left != nil {
		leftMostParent = leftMost
		leftMost = leftMost.Left
	}

	leftMostParent.Left = leftMost.Right
	leftMost.Left = currentNode.Left
	leftMost.Right = currentNode.Right

	// 刪的是root節點
	if preNode == nil {
		root = leftMost
		return root
	}

	if leftMost.Val < preNode.Val {
		preNode.Left = leftMost
	} else {
		preNode.Right = leftMost
	}

	return root
}

Runtime: 12 ms, faster than 86.46% of Go online submissions for Delete Node in a BST.
Memory Usage: 7.1 MB, less than 96.88% of Go online submissions for Delete Node in a BST.

大家在leetcode的soultion可以找到非常簡潔的做法，有興趣可以上去看，不過更不好理解就是了XD

終於講完二元樹的新增刪除走訪了QQ
鏈結的概念一定要先搞懂，不然樹會很難理解
今天先這樣~Bye~~